package MyListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 自己造一个优先队列的比较方法，优先队列存入的是链表，通过比较头节点的值进行排序。
 * 构造链表时，每次取出队首链表，去除头节点后再插入队列中。
 */

/**
 * Java 优先队列
 * add(E e)//将指定的元素插入此优先级队列。
 * clear()//清空
 * contains(Object o) // 如果包含指定元素返回true
 * iterator()//返回在此队列中的元素上进行迭代的迭代器。
 * offer(E e) // 将指定元素插入此优先队列
 * peek() // 获取第一个元素，及最小或最大元素
 * poll() // 获取并移除第一个
 * remove(Object o) // 移除指定元素
 * size() // 返回元素个数
 *
 * offer 和 add
 * 相同点：都是添加元素成功时，都返回true
 * 不同点：添加不成功时，add方法会抛出异常让你处理，offer方法只是直接返回false。
 */
public class Leetcode0023 {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode cur = new ListNode();
        ListNode ans = cur;
        if(lists.length == 0) return ans.next;
//        PriorityQueue<ListNode> q = new PriorityQueue<>(new Comparator<ListNode>(){
//            public int compare(ListNode l1, ListNode l2){
//                return l1.val - l2.val;
//            }
//        });
        PriorityQueue<ListNode> q = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
        for(int i = 0; i < lists.length; i++){
            if(lists[i] != null) q.offer(lists[i]);
        }
        while(!q.isEmpty()){
            cur.next = q.poll();
            cur = cur.next;

            ListNode tmp = cur.next;
            if(tmp != null) q.offer(tmp);
        }
        return ans.next;
    }
}
